\section{最佳有理逼近}
用有理数 (分数) 逼近无理数， 也称为 Diophantus 逼近 (Diophantine approximation). 无理数 $\alpha$ 的连分数的渐近分数 $p_{n} / q_{n}$ 是对 $\alpha$ 的很好的有理逼近， 在某种意义上是最佳逼近。 上节已证明
\[
  \left|\alpha-\frac{p_{n}}{q_{n}}\right| \leqslant \frac{1}{q_{n} q_{n+1}}<\frac{1}{q_{n}^{2}}.
\]

\begin{theorem}%定理1
正实数 $\alpha$ 的连分数 的任两个相邻渐近分数中， 必有一个 $\left(\right.$ 记为 $\left.\frac{p_{n}}{q_{n}}\right)$ 满足
\[
\left|\alpha-\frac{p_{n}}{q_{n}}\right|<\frac{1}{2 q_{n}^{2}}
\]
特别可知， 存在无限多既约分数 $\frac{p}{q}$ 使 $\left|\alpha-\frac{p}{q}\right|<\frac{1}{2 q^{2}}$.
\end{theorem}

\begin{proof}
 若有相邻渐近分数 $\frac{p_{n+1}}{q_{n+1}}, \frac{p_{n}}{q_{n}}$ 不满足定理， 因它们分居 $\alpha$ 两侧， 故
\[
\begin{aligned}
\frac{1}{q_{n} q_{n+1}} & =\left|\frac{p_{n+1} q_{n}-p_{n} q_{n+1}}{q_{n} q_{n+1}}\right|=\left|\frac{p_{n+1}}{q_{n+1}}-\frac{p_{n}}{q_{n}}\right|=\left|\frac{p_{n+1}}{q_{n+1}}-\alpha\right|+\left|\alpha-\frac{p_{n}}{q_{n}}\right| \\
& \geqslant \frac{1}{2 q_{n+1}^{2}}+\frac{1}{2 q_{n}^{2}}=\frac{q_{n}^{2}+q_{n+1}^{2}}{2 q_{n}^{2} q_{n+1}^{2}}
\end{aligned}
\]
故 $2 q_{n} q_{n+1} \geqslant q_{n}^{2}+q_{n+1}^{2},\left(q_{n+1}-q_{n}\right)^{2} \leqslant 0 . n>0$ 时矛盾。 查 $n=0$ 时也矛盾。 证毕。
\end{proof}

\begin{theorem}%定理2
(1) 正实数 $\alpha$ 的连分数的任三个相邻渐近分数中， 必有一个 (记为 $\left.\frac{p_{n}}{q_{n}}\right)$ 满足
\[
\left|\alpha-\frac{p_{n}}{q_{n}}\right|<\frac{1}{\sqrt{5} q_{n}^{2}}
\]
 (2) 对任一实数 $\alpha$, 存在无限多分数 $\frac{p}{q}$ 使
\[
\left|\alpha-\frac{p}{q}\right|<\frac{1}{\sqrt{5} q^{2}}
\]
 (3) 上述上限 $\frac{1}{\sqrt{5} q^{2}}$ 不能再改进。
\end{theorem}

\begin{proof}
 若定理不成立， 则有
\[
\begin{gathered}
\left|\alpha-\frac{p_{k}}{q_{k}}\right| \geqslant \frac{1}{\sqrt{5} q_{k}^{2}}(\text { 对 } k=n, n+1, n+2) . \\
\frac{1}{q_{n} q_{n+1}}=\left|\frac{p_{n}}{q_{n}}-\frac{p_{n+1}}{q_{n+1}}\right|=\left|\alpha-\frac{p_{n}}{q_{n}}\right|+\left|\alpha-\frac{p_{n+1}}{q_{n+1}}\right| \geqslant \frac{1}{\sqrt{5} q_{n}^{2}}+\frac{1}{\sqrt{5} q_{n+1}^{2}}, \\
\frac{\sqrt{5}+1}{2}+\frac{2}{\sqrt{5}+1}=\frac{\sqrt{5}+1}{2}+\frac{\sqrt{5}-1}{2}=\sqrt{5} \geqslant \frac{q_{n+1}}{q_{n}}+\frac{q_{n}}{q_{n+1}},
\end{gathered}
\]
\[
\frac{\sqrt{5}+1}{2}>\frac{q_{n+1}}{q_{n}}
\]
最后式因 $x+\frac{1}{x}$ 为增函数 (当 $x>1$ ) 且 $\sqrt{5}$ 是无理数。 同理得 $\frac{\sqrt{5}+1}{2}>\frac{q_{n+2}}{q_{n+1}}$. 与下式矛盾：
\[
\frac{q_{n+2}}{q_{n+1}}=\frac{a_{n+2} q_{n+1}+q_{n}}{q_{n+1}}=a_{n+2}+\frac{q_{n}}{q_{n+1}}>1+\frac{\sqrt{5}-1}{2}=\frac{\sqrt{5}+1}{2}
\]
 (2) 由 (1) 即得。

(3) $\alpha=\frac{\sqrt{5}-1}{2}$ 为反例。 假若上限 $\frac{1}{\sqrt{5} q^{2}}$ 可改进， 则有分数 $\frac{p}{q}$ 和 $C>\sqrt{5}$ 使 $\frac{\sqrt{5}-1}{2}=\frac{p}{q}+\frac{1}{C q^{2}}, \quad$ 即 $\frac{\sqrt{5} q}{2}-\frac{1}{C q}=p+\frac{q}{2}$.
平方之， 得
\[
\frac{1}{C^{2} q^{2}}-\frac{\sqrt{5}}{C}=p^{2}+p q-q^{2}
\]
$q$ 充分大时， $\left|\frac{1}{C^{2} q^{2}}-\frac{\sqrt{5}}{C}\right|<1$. 故整数 $p^{2}+p q-q^{2}=0$, 即 $(2 p+q)^{2}=5 q^{2}$, 不可能。
\end{proof}

\begin{theorem}%定理3
(最佳逼近) 设 $p_{n} / q_{n}$ 是 $\alpha$ 的连分数的第 $n$ 个渐近分数。 若
\[
|q \alpha-p| \leqslant\left|q_{n} \alpha-p_{n}\right| \quad \text { 且 } 0<q<q_{n+1},
\]
则 $p / q=p_{n} / q_{n}$.
\end{theorem}

\begin{proof}
 因为 $D=p_{n} q_{n+1}-p_{n+1} q_{n}=(-1)^{n+1}$ (上节定理 1(1)), 故如下方程组系数方阵的行列式为 $D=(-1)^{n+1}$, 有整数解 $x, y$ :
\[
\left\{\begin{array}{l}
p_{n} x+p_{n+1} y=p \\
q_{n} x+q_{n+1} y=q
\end{array}\right.
\]
注意 $x y \leqslant 0$, 否则由第 2 个方程知 $q>q_{n+1}$, 与定理条件矛盾。 又由上节定理 1 (3) 知
\[
\alpha-p_{n} / q_{n} \text { 与 } \alpha-p_{n+1} / q_{n+1}
\]
异号。 故 $x\left(q_{n} \alpha-p_{n}\right)$ 与 $y\left(q_{n+1} \alpha-p_{n+1}\right)$ 同号。 于是
\[
\begin{gathered}
q \alpha-p=\left(q_{n} x+q_{n+1} y\right) \alpha-\left(p_{n} x+p_{n+1} y\right)=x\left(q_{n} \alpha-p_{n}\right)+y\left(q_{n+1} \alpha-p_{n+1}\right) \\
|q \alpha-p|=\left|x\left(q_{n} \alpha-p_{n}\right)\right|+\left|y\left(q_{n+1} \alpha-p_{n+1}\right)\right| .
\end{gathered}
\]
此式需不超过 $\left|q_{n} \alpha-p_{n}\right|$, 只能 $|x|=1$ 且 $y=0$; 或者 $x=0$. 后者导致 $q_{n+1} y=q$,与条件 $0<q<q_{n+1}$ 矛盾。 前者导致 $p_{n}=p, q_{n}=q$.
\end{proof}

\begin{theorem}%定理4
若 $p, q$ 为正整数， 而
\[
\left|\alpha-\frac{p}{q}\right|<\frac{1}{2 q^{2}}
\]
则 $p / q$ 是 $\alpha$ 的连分数的渐近分数。
\end{theorem}

\begin{proof}
 不妨设 $p, q$ 互素， $q>0$. 若 $p / q \neq p_{n} / q_{n}(\alpha$ 的连分数的渐近分数， 对任意 $n$ ), 则存在 $n$ 使 $q_{n}<q<q_{n+1}$. 如果 $|q \alpha-p| \leqslant\left|q_{n} \alpha-p_{n}\right|$, 则有上述定理知矛盾。 故可设
\[
|q \alpha-p|>\left|q_{n} \alpha-p_{n}\right|
\]
从而
\[
\begin{gathered}
\left|q_{n} \alpha-p_{n}\right|<\left|\alpha-\frac{p}{q}\right| q<\frac{q}{2 q^{2}}=\frac{1}{2 q} . \\
\left|\frac{p}{q}-\frac{p_{n}}{q_{n}}\right| \leqslant\left|\alpha-\frac{p}{q}\right|+\left|\alpha-\frac{p_{n}}{q_{n}}\right|<\frac{1}{2 q^{2}}+\frac{1}{2 q_{n} q} \leqslant \frac{1}{2 q_{n} q}+\frac{1}{2 q_{n} q}=\frac{1}{q_{n} q}
\end{gathered}
\]
但 $\left|\frac{p}{q}-\frac{p_{n}}{q_{n}}\right|=\frac{\left|p q_{n}-q p_{n}\right|}{q_{n} q}$, 分子为整数， 又需小于 1 , 故只能为 0 , 从而
\[
p / q=p_{n} / q_{n}
\]
\end{proof}


\begin{theorem}%定理5
(Legendre) 设正整数 $p, q$ 满足 $\left|\alpha-\frac{p}{q}\right|<\frac{1}{q^{2}}$, 展开
\[
\frac{p}{q}=\left[a_{0}, \cdots, a_{n-1}\right]=\frac{p_{n-1}}{q_{n-1}}
\]
(使 $(-1)^{n-1}$ 与 $\alpha-\frac{p}{q}$ 同号), 则 $\frac{p}{q}$ 是 $\alpha$ 的连分数渐近值当且仅当
\[
\left|\alpha-\frac{p}{q}\right| q^{2} \leqslant \frac{q_{n-1}}{q_{n-1}+q_{n-2}}
\]
\end{theorem}

\begin{proof}
 记 $\alpha-\frac{p}{q}=\frac{ \pm \theta}{q^{2}}, 0<\theta<1$. 亦即 $\alpha-\frac{p_{n-1}}{q_{n-1}}=\frac{ \pm \theta}{q_{n-1}^{2}}$. 由下式定义 $\beta$ :
\[
\alpha=\frac{p_{n-1} \beta+p_{n-2}}{q_{n-1} \beta+q_{n-2}} \text {, 即 } \beta=\frac{p_{n-2}-\alpha q_{n-2}}{\alpha q_{n-1}-p_{n-1}}
\]
（亦即 $\alpha=\left[a_{0}, \cdots, a_{n-1}, \beta\right]$ ). 则
\[
\frac{ \pm \theta}{q_{n-1}^{2}}=\alpha-\frac{p_{n-1}}{q_{n-1}}=\frac{p_{n-1} \beta+p_{n-2}}{q_{n-1} \beta+q_{n-2}}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1)^{n-1}}{\left(q_{n-1} \beta+q_{n-2}\right) q_{n-1}}
\]
$p / q$ 的连分数有两种表示法， 依 $n$ 的奇偶性可选择使上述 $\pm 1=(-1)^{n-1}$, 故得
\[
\theta=\frac{q_{n-1}}{q_{n-1} \beta+q_{n-2}}, \quad \beta=\frac{q_{n-1}-\theta q_{n-2}}{\theta q_{n-1}}
\]
因 $0<\theta<1$, 故 $\beta>0$. (1) 若 $\beta \geqslant 1$, 则 $\beta=t_{n}$ 是 $\alpha$ 连分数的尾项， 即知 $\frac{p}{q}=\frac{p_{n-1}}{q_{n-1}}$ 为 $\alpha$的渐近分数。 (2) 若 $\beta<1$, 则 $\left[a_{n-1}, \beta\right]=a_{n-1}+\frac{1}{\beta}=\left(a_{n-1}+c\right)+\gamma_{n}$, 其中 $c$ 是 $1 / \beta$的整数部分， 记 $a_{n-1}+c=a_{n}^{\prime}$, 则
\[
\alpha=\left[a_{0}, \cdots, a_{n-1}, \beta\right]=\left[a_{0}, \cdots, a_{n-1}^{\prime}, \cdots\right]
\]
此时 $\frac{p}{q}=\left[a_{0}, \cdots, a_{n-1}\right]$ 不是 $\alpha$ 的渐近分数。
\end{proof}

因为 $\frac{q_{n-1}}{q_{n-1}+q_{n-2}}>\frac{q_{n-1}}{q_{n-1}+q_{n-1}}=\frac{1}{2}$, 故由定理 5 立得定理 4.

\begin{theorem}%定理6
若 $p, q$ 为正整数， 而
\[
\left|p^{2}-q^{2} \alpha^{2}\right|<\alpha
\]
则 $p / q$ 是 $\alpha$ 的连分数的渐近分数。
\end{theorem}

\begin{proof}
 记 $q^{2} \alpha^{2}-p^{2}= \pm \theta \alpha, 0 \leqslant \theta<1$. 则 $q \alpha-p= \pm \theta \alpha /(q \alpha+p)$, 故
\[
r= \pm q(q \alpha-p)=\theta \alpha q /(q \alpha+p)=\theta \alpha q_{n-1} /\left(q_{n-1} \alpha+p_{n-1}\right)>0
\]
其中 $p / q=\left[a_{0}, \cdots, a_{n-1}\right]=p_{n-1} / q_{n-1}, \pm 1=(-1)^{n-1}$, 如定理 5. 因为当 $n \geqslant 2$ 时显然有
\[
1 /\left(q_{n-1} \alpha+p_{n-1}\right)<1 \leqslant q_{n-1}-q_{n-2}
\]
故
\[
\pm \theta \alpha /\left(q_{n-1} \alpha+p_{n-1}\right)<\alpha\left(q_{n-1}-q_{n-2}\right)
\]
左边即是 $q_{n-1} \alpha-p_{n-1}$ (在证明开始的公式中代人 $p / q=p_{n-1} / q_{n-1}$ ), 故得
\[
\begin{aligned}
& \alpha q_{n-1}-p_{n-1}<\alpha\left(q_{n-1}-q_{n-2}\right), \\
& \alpha\left(q_{n-1}+q_{n-2}\right)<q_{n-1} \alpha+p_{n-1}
\end{aligned}
\]
\[
\theta \alpha\left(q_{n-1}+q_{n-2}\right)<q_{n-1} \alpha+p_{n-1}
\]
此式对 $n=2$ 也成立， 因 $\theta \alpha q_{0}=\theta \alpha<\alpha<p_{1}$. 故
\[
r=\theta \alpha q_{n-1} /\left(q_{n-1} \alpha+p_{n-1}\right)<q_{n-1} /\left(q_{n-1}+q_{n-2}\right)
\]
由定理 5 知， 定理得证。
\end{proof}

\begin{example}%例1
对 $\sqrt{3}=[1, \overline{1,2}]$ 的渐近值表 (上节例 2), 再加人近似分数 $p / q$ （对 $q=1,2,3, \cdots$. 基于 $\sqrt{3} \approx p / q, p$ 可由 $q$ 决定），连同 $\sqrt{3}-p / q$ 和 $|q \sqrt{3}-p|$ 列表如下。

$\sqrt{3}$ 的近似分数 $p / q$ 及误差表

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c}
\hline
$\frac{p}{q}$ & $\frac{1}{1}$ & $\frac{2}{1}$ & $\frac{3}{2}$ & $\frac{5}{3}$ & $\frac{7}{4}$ & $\frac{9}{5}$ & $\frac{10}{6}$ & $\frac{12}{7}$ & $\frac{14}{8}$ & $\frac{16}{9}$ & $\frac{17}{10}$ & $\frac{19}{11}$ & $\ldots$ \\
\hline
$=\frac{p_{n}}{q_{n}} ?$ & $\frac{p_{0}}{q_{0}}$ & $\frac{p_{1}}{q_{1}}$ &  & $\frac{p_{2}}{q_{2}}$ & $\frac{p_{3}}{q_{3}}$ &  &  &  &  &  &  & $\frac{p_{4}}{q_{4}}$ & $\ldots$ \\
\hline
$|q \sqrt{3}-p| \approx 0.73$ & 0.27 & 0.46 & 0.196 & 0.07 & 0.34 &  & 0.124 &  & 0.4 & 0.3 & 0.053 & $\ldots$ &  \\
\hline
$\sqrt{3}-\frac{p}{q} \approx$ & 0.73 & -0.27 & 0.23 & 0.065 & -0.0179 & -0.068 &  & -0.017765 &  & -0.045 & 0.03 & -0.005 & $\ldots$ \\
\hline
\end{tabular}
\end{center}
\end{example}

\begin{remark}%注记1
上述几个定理明确了“连分数的渐近分数是最佳有理逼近”这一笼统说法的含义。 衡量 $p / q$ 是否为 $\alpha$ 的最佳逼近 (best approximation), 常用
\[
|q \alpha-p| \text { 或 }|\alpha-p / q|
\]
是否最小 (在分母不超过 $q$ 的所有分数中) 为准则。 前一准则 (即定理 3 所用)更严格合理 (因为考虑到了分母的大小). 例如， 从例 1 表可见， 若按后一准则， 则 $\frac{3}{2}$ 和 $\frac{12}{7}$ 也皆最佳 (但均非连分数的渐近分数), 而用前一准则衡量则皆不是。 故定理 3 说明， 以 $|q \alpha-p|$ 最小为准则， 则最佳逼近恰为简单连分数的渐近分数。 若以 $|\alpha-p / q|$ 最小为准则， 则有渐近分数之外的 “最佳”逼近，例如上述 $\frac{3}{2}$ 和 $\frac{12}{7}$, 它们都是之前两个渐近分数的“中间数” $\left(\frac{12}{7}=\frac{5+7}{3+4}\right.$ 是 $\frac{5}{3}$ 和 $\frac{7}{4}$ 的中间数 $)$, 被称为半渐近分数。

再如， $\mathrm{e}=2.718281828459045235 \cdots$ 的简单连分数为
\[
[2,1,2,1,1,4,1,1,6,1,1,8,1, \cdots],
\]
按 $|q \alpha-p|$ 最小准则的最佳逼近为 $3,8 / 3,11 / 4,19 / 7,87 / 32, \cdots$. 而按
$|\alpha-p / q|$ 最小准则， 则最佳逼近为

$3,5 / 2,8 / 3,11 / 4,19 / 7,30 / 11,49 / 18,68 / 25,87 / 32, \cdots$.
\end{remark}

几何方法可以更好地理解有理逼近。 将实数 $\alpha$ 对应于平面上直线 $L_{\alpha}: y=$ $\alpha x$, 实数 $\alpha$ 即是直线 $L_{\alpha}$ 的斜率。 将有理数 $p / q$ 对应于整点 $(q, p)$ （整点即是坐标为整数的点。 也可将 $p / q$ 对应于过整点 $(q, p)$ 的直线 $y=(p / q) x)$. 整点 $(q, p)$ 到直线 $L_{\alpha}$ 的距离为
\[
d=\frac{|\alpha q-p|}{\sqrt{\alpha^{2}+1}}
\]
(因为点 $\left(x_{0}, y_{0}\right)$ 到直线 $a x+b y+c=0$ 的距离为 $\left|a x_{0}+b y_{0}+c\right| / \sqrt{a^{2}+b^{2}}$ ). 不计常数倍 $\sqrt{\alpha^{2}+1}$, 此距离正是定理 3 衡量逼近程度的距离。 故定理 3 可叙述为

\begin{theorem*}[定理 3' (最佳逼近)] 设直线 $y=\alpha x$ 的斜率 $\alpha$ 为无理数， $p_{n} / q_{n}$ 为 $\alpha$ 的连分数的渐近分数。 若有点 $(q, p)$ 比 $\left(q_{n}, p_{n}\right)$ 离此直线更近且 $q<q_{n+1}$, 则
\[
(q, p)=\left(q_{n}, p_{n}\right)
\]
\end{theorem*}

我们看到， 定理 3 证明的关键一步， 即表 $p, q$ 为 $p_{n} x+p_{n+1} y, q_{n} x+q_{n+1} y$,即是表向量 $(q, p)$ 为向量 $\left(q_{n}, p_{n}\right)$ 和 $\left(q_{n+1}, p_{n+1}\right)$ 的线性组合， 其可以表示恰说明了后两个向量是整点向量集的生成元。

这种几何方法本质上是射影几何， 将实数 $\alpha$ 看做过原点的直线 $L_{\alpha}$ (或直线上的点集), $\alpha$ 是无理数当且仅当 $L_{\alpha}$ 不过整点。 有理逼近即是过整点的直线对于不过整点直线的逼近。

